package org.dse.web;

import java.util.*;

/**
 * Kleinberg's hypertext-induced topic selection <a
 * href="http://citeseer.ist.psu.edu/kleinberg99authoritative.html">(HITS)</a>
 * algorithm is a very popular and effective algorithm to rank documents based
 * on the link information among a set of documents. The algorithm presumes that
 * a good hub is a document that points to many others, and a good authority is
 * a document that many documents point to.
 * 
 * Hubs and authorities exhibit a mutually reinforcing relationship: a better
 * hub points to many good authorities, and a better authority is pointed to by
 * many good hubs.
 * 
 * Because the HITS algorithm ranks documents only depending on the in-degree
 * and out-degree of links, it will cause problems in some cases. For example,
 * <a href="http://citeseer.ist.psu.edu/bharat98improved.html"> Improved
 * Algorithms for Topic Distillation in a Hyperlinked Environment</a> presents
 * two problems: mutually reinforcing relationships between hosts and topic
 * drift. Both can be solved or alleviated by adding weights to documents. The
 * first problem can be solved by giving the documents from the same host much
 * less weight, and the second problem can be alleviated by adding weights to
 * edges based on text in the documents or their anchors.
 * 
 * @author zhangchen
 * 
 */
public class HITS {

	/** The data structure containing the Web linkage graph */
	private WebGraph graph;

	/** A <code>Map</code> containing the Hub score for each page */
	private Map<String, Double> hubScores;

	/** A <code>Map</code> containing the Authority score for each page */
	private Map<String, Double> authorityScores;

	/**
	 * Constructor for HITS.
	 * 
	 * @param graph
	 *            The data structure containing the Web linkage graph
	 */
	public HITS(WebGraph graph) {
		this.graph = graph;
		this.hubScores = new HashMap<String, Double>();
		this.authorityScores = new HashMap<String, Double>();

		Set<String> linkUrls = graph.availableLink();

		for (String url : linkUrls) {
			hubScores.put(url, 1.0);
			authorityScores.put(url, 1.0);
		}
		computeHITS();
	}

	/**
	 * Computes the Hub and Authority scores for all the nodes in the Web Graph.
	 * In this method, the maximum number of iterations of the algorithm is set
	 * to 25.
	 */
	public void computeHITS() {
		computeHITS(25);
	}

	/**
	 * Computes the Hub and Authority scores for all the nodes in the Web Graph.
	 * 
	 * Given a Web graph, an iterative calculation is performed on the value of
	 * authority and value of hub. For each page p, the authority value of page
	 * p is the sum of hub scores of all the pages that points to p, the hub
	 * value of page p is the sum of authority scores of all the pages that p
	 * points to.
	 * 
	 * Iteration proceeded on the neighborhood graph until the values converged.
	 * 
	 * @param iter
	 *            The maximum number of iterations for the algorithm
	 */
	public void computeHITS(int numIterations) {
		Set<String> linkUrls = graph.availableLink();

		boolean change = true;
		while ((numIterations--) > 0 && change) {
			change = false;
			for (String url : linkUrls) {
				Set<String> inlinks = graph.inLinks(url);
				Set<String> outlinks = graph.outLinks(url);
				double authorityScore = 0;
				double hubScore = 0;

				for (String inlink : inlinks) {
					authorityScore += hubScores.get(inlink).doubleValue();
				}
				for (String outlink : outlinks) {
					hubScore += authorityScores.get(outlink).doubleValue();
				}

				Double authorityScore2 = authorityScores.get(url);
				Double hubScore2 = hubScores.get(url);
				if (Math.abs(authorityScore2.doubleValue() - authorityScore) > 0.00000001) {
					change = true;
					authorityScores.put(url, new Double(authorityScore));
				}
				if (Math.abs(hubScore2.doubleValue() - hubScore) > 0.00000001) {
					change = true;
					hubScores.put(url, new Double(hubScore));
				}
			}
		}
	}

	/**
	 * Returns the Hub score associated with a given link
	 * 
	 * @param link
	 *            The url for the link
	 * @return The Hub score associated with the given link
	 */
	public double hubScore(String link) {
		Double score = hubScores.get(link);
		if (score != null)
			return score.doubleValue();
		else
			return 0;
	}

	/**
	 * Initializes the Hub score associated with a given link.
	 * 
	 * @param link
	 *            The url for the link
	 * @param value
	 *            The Hub score to assign
	 */
	public void initializeHubScore(String link, double value) {
		hubScores.put(link, new Double(value));
	}

	/**
	 * Returns the Authority score associated with a given link
	 * 
	 * @param link
	 *            The url for the link
	 * @return The Authority score associated with the given link
	 */
	public double authorityScore(String link) {
		Double score = authorityScores.get(link);
		if (score != null)
			return score.doubleValue();
		else
			return 0;
	}

	/**
	 * Initializes the Authority score associated with a given link.
	 * 
	 * @param link
	 *            The url for the link
	 * @param value
	 *            The Authority score to assign
	 */
	public void initializeAuthorityScore(String link, double value) {
		authorityScores.put(link, new Double(value));
	}
}
